The present invention is directed to the field of cryptography. It is more specifically related to the field of digital signature technology.
A digital signature is a fundamental cryptographic primitive which, in the digital setting, generally serves the same purpose as a handwritten signature in the real world setting. Namely, it binds, in an unforgeable, non-repudiable manner, the identity of the signer to the information being signed.
The mechanisms of applying and using public-key based digital signature technology however, are quite different than those used for handwritten signatures. Firstly the digital signature itself is a mathematical function of the message being signed and a private key known only to the signer. Thus, unlike a handwritten signatures, every digital signature employed by an entity is very different from its other signatures, since the underlying message being signed is likely to be different. Verification of a digital signature, therefore, is also very different from its handwritten counterpart. Instead of examining the similarity between the signature on a message and a sample signature of the signer, the verifier applies a mathematical function on the message, the signature and a publicly known key of the signer. The publicly known key is known to correspond to the signer""s privately held key. The system works as long as it is infeasible to compute the private key from the publicly known key, and without the private key it is infeasible to compute the signature on any new message. Therefore, whereas everyone is able to verify the signatures using the public key, only the owner of the private key can compute digital signatures.
The above is a description of how public key signatures work in theory. However, to make such signatures useful in practice, several additional steps, cryptographic primitives and infrastructure are required. We now describe some of these additional steps, primitives and infrastructure since they have a direct bearing on this invention.
From the description of the generation, signing and verification process above, it should be clear that a digital signature only binds the signature to the owner of a private key corresponding to the public key used in the verification process. Since private-public key pairs are just mathematical objects which can be generated by anyone, to serve any useful legal and/or other purpose, there should also be a binding between the public key and the real-world identity of the owner of the corresponding private key. In practice this is done by means of another digital object called a public key certificate. The certificate (or chain of certificates) is essentially a statement binding the real-world identity of a signer with a public key, together with a digital signature (or chain of digital signatures) from a trusted entity vouching for the veracity of the binding statement. The trusted entity is referred to as a certification authority. Since the certification authority""s public key is well known, this provides a way for another entity which trusts the certification authority, to verify that indeed the signer with a certain real-life identity is in possession of the private key corresponding to the public key. This other entity can verify the binding between the signer""s identity and public key by verifying the certification authority""s signature on the binding object.
There is yet another important practical issue relating to the use of digital signatures. In popular public key signature schemes such as the RSA algorithm, the DSA algorithm etc, once the public/private key for a signer is chosen, the core signature algorithm can only be applied to message blocks of a certain fixed size. However, it is impractical for entities to have multiple certified public keys for all possible message block sizes. Also, computing signatures for very large message-block sizes is very time consuming. In practice, core signature schemes are used in conjunction with another cryptographic primitive known as a cryptographic hash function. A cryptographic hash function is a publicly known function that takes in an arbitrary sized message as an argument and produces a fixed sized output. This output is said to be the cryptographic hash of the message. The hash function has a property of being collision resistant. A function is collision resistant if it is infeasible to come up with two different inputs upon which the function produces the same output. Examples of cryptographic hash functions include SHA-1 and MD5 which produce 160-bit and 128-bits outputs respectively.
With a collision resistant hash function, a signer can sign any arbitrarily sized message with a single private key by applying the signature algorithm only to the cryptographic hash of the message. Similarly, a verifier can verify a signature on a message by applying the signature verification algorithm on the cryptographic hash of the message. Since it is infeasible for anybody (including the signer, the verifier or any other third party) to compute two different messages which have the same cryptographic hash, with respect to unforgeability and non-repudiation, a signature on the hash behaves like a signature on the actual message.
In many cases, another cryptographic primitive called a Target Collision Resistant (TCR) hash function can be used in the place of collision resistant hash function in the signature compution process for arbitrary messages. TCR hash functions may be referred to as universal one-way hash functions. Target Collision Resistance can be viewed as a weaker requirement than collision resistance, but is nevertheless considered to be good enough for signatures. A target collision resistant function is a publicly known function that takes as input a fixed sized message and a fixed sized key and produces an output of some fixed size. The cryptographic property required of a TCR function T is that given its description, it is infeasible for someone to come up with any message M1, such that, when the function T is computed with a randomly chosen key K, it becomes feasible for that someone to compute some other message M2, such that the value of T on M1 and K coincides with the value of T on M2 and K. The point to note in the definition of a TCR function is that the key K is randomly chosen only after M1 has been chosen. Indeed, it is quite possible that if K were to be chosen first then it may be quite easy to produce a collision, i.e., two messages M1 and M2 such that T on K and M1 coincides with T on K and M2. Thus, the TCR requirements of a function are less burdensome than the requirements of collision resistance from a keyless function which prohibits easy computation for any collision whatsoever. Therefore, candidates for TCR functions are expected to be easier to design than candidates for collision resistant hash functions.
TCR functions are suitable for use in signatures in the following way. In order to sign a message m, which in the most general setting could have been chosen by someone other than the signer, the signer randomly picks a key k, computes the TCR function on m and k and then signs the output resulting from applying the TCR function together with k using any available digital signature scheme. If the available digital signature scheme is unforgeable, then the scheme involving TCR function retains the property that it is not feasible for anyone else to forge signatures based on it. Hence they cannot be repudiated. It should be noted that in the case of TCR based signatures, the signer can come up with two different messages which have the same signature by choosing the messages after choosing the key to the TCR function, whereas in the case of collision-resistant hash functions, even the signer cannot do so.
We now briefly describe another cryptographic primitive known as a commitment scheme. Although, prior to the present invention commitment schemes are unrelated to digital signatures, they are described here, since they will be shown to be relevant to the present invention.
A commitment scheme is a two stage protocol involving a committer and one or several verifiers. Informally, the goal of a commitment protocol is to model some of the properties of a sealed box or envelope in real-life. The sealed box may, for example, include a commiters bid for an object. At the first stage of the protocol, the verifiers are interested in having the entity/committer irrevocably make a choice from a set of options. The committer is amenable to making such a choice but at this stage does not want the verifiers to know what choice he has made. This situation often arise in real-life in situations in which a party (commiter) wants to make a bid for an object without disclosing the bid to anyone else. Everyone participating in the bidding would require that each party commit themselves to the bid so that no-one should be able to change their bids at a later time. The committer then follows the commitment protocol and produces a digital message, known as a commitment. This commitment message has the property that it forever binds the committer to a choice or bid, without disclosing any information about the specific choice the committer has made. This process is analogous, in the real-world to the committer writing his choice on piece of paper and putting the paper in a publicly displayed opaque envelope or box and either sealing the envelope or locking the box. At a later time, when all parties are interested in publicizing the committed choice, the committer produces a committment opening string which together with the commitment message reveals the choice that was originally committed. This in real-life would correspond to the commiter opening the seal or lock to reveal the contents of the envelope/box. This type of commitment is hereinafter referred to as a regular-commitment. (The reason being that this invention will describe a new cryptographic primitive which will be termed a TCR-commitment, which is very similar to a regular-commitment but nevertheless has slightly weaker properties.)
After having described public key signatures, cryptograpic hash functions, TCR functions and regular-commitment schemes we now describe some of the shortcomings of current digital signature technology which the present invention addresses.
One of the main drawbacks of current digital signature technology which prevents its deployment in many applications is performance. Public key signatures using acceptable algorithms and key-lengths are very compute-intensive to generate and/or to verify. For example, even a high end workstation such as a 200 MHz PowerPC 604e based RS/6000 can generate only 50 or so 1024 bit RSA signatures per second. For many applications such a rate is unacceptably slow.
One such application is secure-multicast. In multicast, a sender can send a single packet to a group of recipients over a network. The network is responsible for delivering the packet to all recipients in the group. Multicast generally permits a far more efficient usage of network bandwidth than the alternative unicast approach in which the sender sends the same packet individually to each of the recipients.
Now consider the problem of authenticating the sender of a multicast packet. In the case of unicast, the sender can append a message authentication code (MAC) to the packet using a key it shares with the recipient. In the case of multicast this does not work since the MAC key would have to be known by all recipients and therefore any recipient can masquerade as the sender. The security exposure of using MACs for authentication in multicast can be significant especially if the multicast group is very large. An approach to solve this problem from a security perspective requires the sender to digitally sign each packet. Any recipient would then be able to authenticate the packet without having the ability to masquerade as the sender. However, due to the poor performance of signature schemes such an approach is not practical. Some multicast applications require a packet rate exceeding 50 packets/s. Most applications which require less throughput, nevertheless cannot devote a significant fraction of the sender""s computing resources to calculating signatures. Also, if a sender is serving multicast data to several multicast groups, the number of public-key signatures that it can perform per second per group is severely limited. Thus this solution is not practically feasible.
Another possible solution is to relax the security requirements for authentication. If a certain amount of risk is acceptable, then one could use a fast but less well-studied signature algorithm, such as those based on Elliptic Curves. This approach would provide fast yet secure authentication only to the degree to which the underlying cryptographic assumptions are valid. However, when these assumptions turn out to be invalid, these schemes may be completely open to compromise.
Another approach to packet authentication when the security requirement is relaxed is to use so-called xe2x80x9casymmetric MACsxe2x80x9d. The basic idea is that one can use a scheme in which multiple Message Authentication Codes (MACs) are appended to each packet. This has the property that the packet can be authenticated by each receiver. It requires at least a threshold of malicious receivers to collude in order to masquerade as a sender. However, the number of MAC""s computed by the sender and attached to the packet needs to be a linear function of the number of colluders that the scheme is supposed to be resilient against. Therefore, even though this scheme may be useful in some scenarios, e.g., when groups are small and problems of collusion can be controlled, it does not work well in scenarios where the multicast group is very large and large collusions are likely to occur or difficult to detect.
When reliability of transmission is not an issue, an approach known as stream signing may be useful. It is used to sign the multicast packets and yet provide strong security guarantees of authentication and nonrepudiation associated with digital signatures. In this approach only one regular signature is transmitted at the beginning of a stream of packets. Each packet either contains a cryptographic hash of the next packet in the stream, or a 1-time public key using which the next packet can be verified. However, this approach cannot tolerate a lost packet, since the information needed to authenticate future packets is lost.
Given that IP-Multicast is generally an unreliable protocol and/or many mulitcast applications such as audio and video delivery are unlikely to require reliability this solution may not be applicable. Also, even if reliability is not an issue this solution requires use of 1-time keys and signatures to be embedded in each data packet. Such keys and signatures are fairly large and can result in a substantial space overhead within each packet which may be unacceptably large. Sometimes, the stream signing overhead can be substantially reduced at the cost of introducing a delay at the sender side and grouping several packets together so as to distribute the overhead into multiple packets. However, delaying and grouping of sender""s packets cannot be done in peer-to-peer interactive multicast applications such as distributed simulations and gaming which are important multicast usage scenarios.
Another approach is useful when a sender is allowed to delay and group together several consecutive packets. In this approach, the sender uses a collision resistant hash function to form an authentication tree from packets collected during a time-interval and signs the root of the authentication tree. Each packet is augmented by the signature on the root and ancillary information. The ancillary information includes hashes of neighboring nodes on the logarithmically long path from the message to the root of the authentication tree. The collected and augmented packets are then sent. This allows each packet to be individually verified at the receiving end.
While this approach is quite effective in client-server scenarios where the server is dedicated to serving a small number of multicast flows, each with reasonably smooth flow rates and strictly enforced bounds on processor loading, it suffer from several practical drawbacks. Firstly, delaying and grouping of sender""s packets is not always possible for many important multicast applications. Secondly, there is still a problem of serving multiple multicast flows. This is best illustrated by the following example. Suppose a server only has enough cycles to perform 10 public key operations per second. Using this approach, such a server could potentially serve hundreds of authenticated packets per second to a single flow with only a minor delay, say a tenth of a second. However, if the same server was required to send only 50 different flows, each with a packet rate of only 1 packet/second (such as serving multiple hand held devices) for a total of 50 packets/second throughput, this will not be possible unless the same signing key and authentication tree data structure is shared across different flows, or an unacceptably long delay of 5 seconds is imposed on each flow. Sharing between flows puts unreasonable constraints on the software architecture at the server side. This restrict the choice of authentication mechanisms and expose privacy issues regarding combining information from different flows. A third problem with the scheme is that the size of the authentication information tacked on to each message is not fixed. The size depends of the short-term packet rate which in many applications is likely highly irregular and bursty. During bursty periods, the packets will be larger. This can cause undesirable side-effects such as increased packet loss due to fragmentation. A fourth problem with the scheme is that it provides no mechanism to smooth out bursty processor loads. In any real system there are periods when the processor has enough free time to calculate 50 signatures/s. However, there are also times when the processor barely has time to calculate 1-2 signatures/s. With the tree approach, there is no way to leverage the idle time of the CPU to help during the time when it is highly loaded. Performance will seriously degrade when the CPU gets loaded.
In one aspect, the present invention addresses the problem caused by the slow speed of public key signature algorithms. It solves the problem of packet authentication for multicast and other scenarios requiring fast, compact digital signatures.
Another aspect of the present invention provides security guarantees required for packet authentication in a way that can handle multiple independent flows, produces authentication fields of fixed size, works in the fully unreliable setting, does not require any packet delays and has the additional property of being able to withstand and smooth over irregular processor loading and bursty packet output rate.
An aspect of the present invention uses a hybrid approach consisting of the signer creating a certificate for the public key of an efficient k-time signature scheme using a regular signature key. The signer then signing up to k messages with the private key corresponding to k-time public key. The time consumed to compute a public key signature is amortized over k signatures.
These and other aspects are provided in a signature scheme wherein a commitment is employed. Other objects and a better understanding of the invention may be realized by referring to the detailed description.